ストレージと検索 from DDIA
Chapter 3. Storage and Retrieval
今度は一段下がったデータモデル、DBの目線からストレージへの保存とその再取得ー即ち検索を見ていく OLTPとOLAPではストレージの構成が全然変わってくる
avashe.iconこっからプリミティブなDBを作り、Step by Stepで改良しながらDBの発明を追っていく
いろいろ省略
本書におけるログは追記のみのレコード列を指している
バイナリなど、人間が読むことを想定したものではないことに注意
インデックスはストレージのreadを高速化するがwriteにインデックス更新分のオーバヘッドが乗る
DBの用途や実測のクエリ比率に応じてインデックスの数や有無を最適化する必要がある
avashe.icon私が面白いと感じたのは実装が単純かつ頻繁な更新に強いkey-valueストア "Hash indexes" kvのinsertとupdateは全てディスクへログとして追記していく
ログが閾値を超えたらログローテートして、それらログセグメント全てを最新の値だけにコンパクションする
コンパクションしてログセグメントが小さくなりすぎた場合は複数のログセグメントをマージする
メモリ上にはログセグメント毎にハッシュマップを用意する
各ハッシュマップはセグメント内の登場するkeyと最新のvalueへのbyte offsetの組を保存する
最も最近のセグメントからkeyを検索していく
ディスクアクセスが一回で済む
keyが全てメモリ上に乗る限りはまんべんなく来るvalueの更新に対してとても強い
幾つか議論すべき点もある
クラッシュからの復旧時、ハッシュマップが揮発した際の処理
例えばレコードを削除したことを忘れるため、単純にハッシュマップ上の処理だけで削除すると復旧時に困る
あるキーの削除を示す(そのキーについてこれ以上遡らせない)レコードを実装する必要がある
tombstoneレコードというらしい
復旧時にログセグメントを全て遡ってハッシュマップを再構築するのは時間が掛かる
Bitcaskでは定期的にマップのスナップショットをとりストレージへ書き込む
中途半端に書き込まれたレコード
BitCaskではチェックサムを先に書き込むことで汚染された部分を無視できるようになっている
並行性制御(Concurrency Control)
ログ追記のみというのはstrictly sequencial orderでとても良い性質
書き込みトランザクションのワーカーを1スレッド、読み込みスレッドは複数スレッドがよくある実装
書き込みが追記のみなのがいい性質をもたらしている
ログがシーケンシャルライトなのでとにかくはやい
HDDではシーケンシャルであることが死活問題
SSDでも幾つかのエクステントをまとめてシーケンシャルライトするのは良い性能を出す
並行性制御とクラッシュリカバリがとても単純になる
値が書き換えられたことを想定しなくてよいのが強い
単純なマージでフラグメンテーションを予防できる
勿論欠点もある
key全体がメモリに乗ることを仮定する
ディスク上だとランダムアクセスのみなのでパフォーマンスががた落ちする
レンジクエリが遅い
一つずつしか調べられず、特殊な仕組みがない
書き込みが単純な追記ではなくなるが、幾つかHash indexesと比べ利点がある
セグメント群がディスクに乗らないサイズでも高速にマージ&コンパクションできる
keyでソートされたことでログセグメント群のマージソートが可能だから
同じkeyが現れたらログセグメントの最も新しい日付を優先するだけ
メモリに乗りきらないkey数を扱える
ログ内ではkeyが辞書順になっているので、indexはsparseでいい
メモリに乗っている辞書順の前後を求め、その範囲を探索する
key valueともに固定なら二分探索できる
多くの場合kvが可変長なのでkeyの粒度が大事(ストレージごとの調節ポイント)
どうせkey間を走査するので、ストレージを意識したチューニングができる
バッファからログをフラッシュする前に圧縮する
各keyが対応する圧縮ブロックを指すようにする
肝心のSSTable構築はどうすんの
任意の順で順次挿入されても常に全体がソートされるようなデータ構造をメモリ上において、ログに書き込む前のバッファとする
Red-Black TreeかAVL Treeが有名なのでここではそれらを仮定
これらをmemtableとよぶ
これは先程までのsparceなbyte offset indexではなくてログのバッファであることに注意
memtableが閾値に到達したらSSTableとしてフラッシュ
memtableは常にソートされているのでこれは簡単
この定期的なフラッシュを1つのログセグメント単位とする
フラッシュ実行中はスナップショットとるなりして並行してタスクを続行する
readリクエストは最初直接memtableを探し、その後各SSTableのインデックスに当たる
SSTable群のマージ&コンパクションはバックグラウンドで
memtable揮発問題はレストア用ログに逐次redoログ残して回避
こっちはクラッシュ時のmemtableレストア用なので順序を意識せず書き込んでOK
SSTableに書き込まれる際にはこれを無視する(まとめて後で消すとか?)
そういう経緯なので、ソートされたファイルをマージしたりコンパクションするストレージエンジンをまとめてLSM的な手法とか、LSM storage engineとか呼ぶ
avashe.iconこの辺微妙に私が整理しきれてないか、原文が濫用気味な気がする
全文検索エンジンのLuceneでも似たような手法が使われている avashe.icon つまり↓条件が揃っている際のストレージとメモリの使い方は似通ってくるってことなんだろうか?
keyがメモリに乗り切らない
valueが大きく、ストレージへの永続化が必要
ストレージが無尽蔵であることを仮定しない(できればコンパクションして乗り切りたい)
現代なら仮想化や分散システムなどのボリュームマネジメントを期待しない、ともいえる
LSM的ストレージのチューニング
keyがDBになかった場合の遅さ解消
最悪memtableと全てのSSTableを見ないと不在が確定しない
False Positiveなので、完全に存在しえないSSTableを枝刈りできる
マージとコンパクションのタイミング
もっとも使われているのはsize-tieredとleveled
LevelDBとRocksDBはleveled
size-tieredは最も小さいセグメントが次点に古く大きいセグメントとマージされる
leveledはまず古さで大きくlevelに分けられ、そのlevelの中でkey rangeごとに小さな複数のSSTableへ分けられる
avashe.iconleveledはデータの温度が採用されているので賢いように見える 冷めたデータほど深いlevelに移り、より大雑把な単位で扱われる
これら微妙な点があろうとも、LSM-treeのアイデア(SSTableとバックグラウンドでのマージ)はシンプルで効率的である
データがメモリに乗りきらずとも十分動作する
SSTableがソート&定期的にマージされているためレンジクエリが効率的である
まとめてメモリからフラッシュされるためSSTableの書き込みはシーケンシャルライトになる
ストレージのハードウェアを意識したインデックス向けのツリー
keyがソートされた固定長のnodeとleafを持つmulti-branch tree
nodeはソートされた<key1>,< key1より大きくkey2より小さい子への参照>, <key2>,... の列
ようは上述したSSTableのスパースなノードと同じことをやってる
あるkeyの値を探す際、ノード内を二分探索しながら範囲を絞りこめる
range queryに強くなる
leafは(key, value)の組
全てのnodeとleafはブロックあるいはページサイズに合わせた固定長である
1ページ=ノードにおける子ページへの参照数をbranching factorとも言う(枝の数でよくない?)
branching factorは1つリファレンスのデータ量とrange boundariesで決まる
avashe.iconrange boundaries説明がないけど、参照の範囲を何分割したいかという話かな
典型的には数百
code: haskell
data Tree key val where
Tree :: !TreeSetup
-> Maybe (Node height key val)
-> Tree key val
-- Nodes are parameterized over the key and value types and are additionally
-- indexed by their height. All paths from the root to the leaves have the same
-- length. The height is the number of edges from the root to the leaves,
-- i.e. leaves are at height zero and index nodes increase the height.
data Node (height :: Nat) key val where
Idx :: { idxChildren :: Index key (Node height key val)
} -> Node ('S height) key val
Leaf :: { leafItems :: Map key val
} -> Node 'Z key val
-- The index is abstracted over the type 'node' of sub-trees. The keys and
-- nodes are stored in separate 'Vector's and the keys are sorted in strictly
-- increasing order. There should always be one more sub-tree than there are
-- keys. Hence structurally the smallest 'Index' has one sub-tree and no keys,
-- but a valid B+-tree index node will have at least two sub-trees and one key.
data Index key node = Index !(Vector key) !(Vector node)
deriving (Eq, Functor, Foldable, Show, Traversable)
-- | Setup of a pure B+-tree.
data TreeSetup = TreeSetup {
minFanout :: Int
, maxFanout :: Int
, minIdxKeys :: Int
, maxIdxKeys :: Int
, minLeafItems :: Int
, maxLeafItems :: Int
} deriving (Show)
Indexを見れば分かる通り、本当なら最少は2つのサブツリーへの参照と1つのkey
ここは篩型を持ち出さないと無理なのでIndex型を受ける関数でassertしていると思われる
Nodeの(height :: Nat)と、'S heightと'Zは型レベル自然数でノードの高さを乗せてるだけなので気にせず
ノード間の参照をword64にしている
必要であればpureなHaskell世界のほうへエンコードするBTreeモナドを作ればよい
1970年代に紹介されると、10年も経たずubiquitousと呼ばれるようになった
ノードがページに収まらなくなったら、そのページを二つに割り、親ノードに値一つと参照二つとしてぶら下げる
avashe.icon やっぱり図がないと木はわからん
https://gyazo.com/6d085011d9429815a42021a82b81f6c1
これでリバランスされているのが分かる
削除はもっと面倒
ほとんどのDBは3~4程度の高さ
$ nkeyで高さは$ O (\log n)になる
4KBページ、branching factor 500のB-Treeは高さ4で256TBに達する
in-place updateの信頼性
LSM-Treeと違い、書き込みデータを書きかえる
つまりindexの参照先を変えず、参照先を変える
in-placeな書き換えは、書き換え途中にシステムがクラッシュした場合を考えなければならない
avashe.icon結局append-onlyなログを作ってる
加えて並行にする際は並行性制御のアルゴリズムを考える必要がある
部分的な木の操作にlatchを使うなど
B-Treeの最適化
広く普及しているのでたくさんの最適化が考案された
編集したいページから遡ってrootまでコピーし、そのコピーを編集する
構造は部分的に共有されており、複数のrootがある
読み手はリクエスト受理時点のconsistencyなスナップショットを読む
この間書き込みがあっても続行できるので並行性制御としても楽
avashe.iconCoWによって並行性制御しやすくなるのは永続データ構造が持つ性質の白眉(Structure Sharing) この本の中盤で再び扱う
省略されたkeyの保存による容量の削減
境界値として振舞える範囲で省略する
avashe.iconbranch factorと深さに応じて省略度合を計算するのかな?
leafページがdisk上にてシーケンシャルに出現するように管理する
range queryが少ないseek数で読めないと速度ががた落ちする
key rangeが狭ければdisk seek rangeとしてもそばにいてほしい
書き換えが進むほどばらけるので、実際これを維持するのは難しい
その辺はLSM的手法の方が優れている
追加のポインタ
典型的には各leafが前後のleafへのポインタを持っている
シーケンシャルに参照したい際有益だから
B-Tree派生ではlog-structuredな手法を取り込んでdisk seekを減らすこともある
B-TreeとLSM-Treeの比較
LSM-Treeはwriteが速い
B-Treeはreadが速い
LSM-Treeは複数のindexやSSTableを見るので遅くなる
しかしワークロードによって話は全然違うので、ベンチマークを少し見たくらいで定性的なことは言えない
ここから幾つか議論
log-structured indexにおいて、一度のデータ書き込み命令に対して複数のディスク書き込みが生じること
B-Treeは最低でも二度書き込む
ログと木のページ
リバランスが生じたらページが3回になるので4回書き込み
LSM storage engine は命令に対しては1回だが、DBのライフタイムによって償却されている書き込みがある
ただしmemtableを採用すると揮発対策で2回になる
不定期にSSTableのマージ&コンパクションがバックグラウンドで走る
writeが激しいシステムにおいてワークロードにおけるディスク書き込みの比率がパフォーマンスボトルネックになる
LSM-TreeはB-Treeよりwriteスループットを高めやすい
ストレージの構成によるがwrite amplificationが少なくなりやすい
SSTableというページより大きい単位でシーケンシャルwriteするのでdiskの特性に適合している
B-Treeはページ単位で参照するためフラグメンテーションしやすく、参照によるデータ量としてのオーバヘッドもある
SSTableはコンパクションやファイル単位での圧縮ができるためデータ量自体がB-Treeより小さくなりやすい
特にleveledだと強い
SSDの場合
磁気ディスク程アクセスパターンによってwriteスループットが変動しない
SSDファームウェアの多くがlog-structured algorithmを採用しランダムwriteをシーケンシャルに置き換える
LSM-Treeのwrite ampの小ささとデフラグは依然大きな利点
データが小さいほど多くのリクエストがさばける
LSM-Treeの欠点
マージ&コンパクションが表のreadとwriteを妨げてしまう
スループットと平均応答時間には微々たる影響でも、高いパーセンタイルでは非常に高いレイテンシを生みうる
B-Treeのパフォーマンスは比較的予測可能である
read&writeリクエストとマージ&コンパクションの両立を予め考えIO帯域幅を確保しないと詰む
後者が前者に間に合わないとストレージオーバーラン
SSTableの典型的な実装ではスロットル機能が無いので、コンパクションが間に合っていない場合に検出できるようモニタリングしよう
B-Treeの利点は各keyがindex内に必ず1つずつ存在すること
LSM-Treeだと異なるログセグメント内に複数ありうる
This aspect makes B-trees attractive in databases that want to offer strong transactional semantics
avashe.iconよくわからんけど、transaction Isolationを考えるうえで都合が良いということっぽい
これはChapter 7でやる
B-Treeは多くのワークロードに対して一貫して良いパフォーマンスを出す
どのストレージエンジンがいいか簡単に分類する方法は無いので、新しいDBが使ってるからLSM-Tree使おう!とはならず、ユースケースの種類に応じてちゃんと試験運用&制約の分析しましょう
検索インデックス
インデックスの先に値を直接埋め込むか、参照にするかでひと悶着ある
参照の先はheap fileと言われる
埋め込むのがclustered index
ホップ数を減らしてパフォーマンスを上げたいから
MySQLのInnoDBは主キーをclustered indexで作り、セカンダリインデックスは参照先がclustered indexの先を指す
(non)clusteredの折衷案がcovering index
部分的にインデックスの先に埋め込む
インデックスに伴うデータの複製はパフォーマンスのトレードオフを起こす
clustered, covering indexが対象
readの高速化、writeと記憶領域のオーバヘッド、トランザクションの一貫性における追加コスト(cpuや開発リソース)
multi-column indexes
複数の列によって定まるインデックスも実装方法が幾つかある
単純に要素を結合してカギとするconcatenated index
結合したインデックスでは二次元の値のrange queryがうまく表現できない
緯度と経度で絞り込むとか
1手法としては多次元の値を1次元に変換する事が考えられる
インメモリDBは単にディスクよりメモリが速いから速いのではない
メモリ-ディスク間という層を取り除き最適化されたアルゴリズムの勝利である
その上でディスクへ追記のみのredoログ(とチェックポイント)でdurabilityは維持できる
RAMCloudプロジェクトはOSSで公開されている分散In-memory DB 近年ではメモリより大きいデータに対応したアーキテクチャも研究されている
ここまではOLTP(OnLine Transaction Processing)、ここからはOLAP(OnLine Analysis Processing)